<?php
// 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字

/**
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5


示例 2:
输入: 1->1->1->2->3
输出: 2->3
 */

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val)
    {
        $this->val = $val;
    }
}

class Solution {
    public function deleteDuplicates($head) {
        if($head == null || $head->next == null) {
            return $head;
        }
        $dummy = new ListNode(-1);
        $dummy->next = $head;
        $p1 = $dummy;
        $p2 = $head;
        while($p2 != null && $p2->next!= null) {
            //初始化的时p1指向的是哑结点，所以比较逻辑应该是p1的下一个节点和p1的下一个节点
            if($p1->next->val != $p2->next->val) {
                $p1 = $p1->next;
                $p2 = $p2->next;
            } else {
                //如果p1、p2指向的节点值相等，就不断移动p2，直到p1、p2指向的值不相等
                while($p2!=null && $p2->next!=null && $p1->next->val == $p2->next->val) {
                    $p2 = $p2->next;
                }
                $p1->next = $p2->next;
                $p2 = $p2->next;
            }
        }
        return $dummy->next;
    }

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function deleteDuplicatesV1($head) {
        if ($head == null || $head->next == null) {
            return $head;
        }

        // 出现次数计数
        $counter = array();
        // 仅仅出现一次的元素
        $number_list = array();

        // 统计元素出现次数
        $curr = $head;
        while ($curr != null) {
            if (isset($counter[$curr->val])) {
                $counter[$curr->val] += 1;
            } else {
                $counter[$curr->val] = 1;
            }
            $curr = $curr->next;
        }

        // 获取仅仅出现一次的元素
        foreach ($counter as $number_item => $number_counter) {
            if ($number_counter == 1) {
                $number_list[] = $number_item;
            }
        }

        // 升序排列
        sort($number_list);

        // 构造新链表
        $new_pre_head = new ListNode(-1);
        $p = $new_pre_head;
        foreach ($number_list as $item) {
            $node = new ListNode($item);
            $p->next = $node;
            $p = $p->next;
        }

        return $new_pre_head->next;
    }
}

$node_1 = new ListNode(1);
$node_2 = new ListNode(2);
$node_3 = new ListNode(3);
$node_4 = new ListNode(4);
$node_5 = new ListNode(5);
$node_1->next = $node_2;
$node_2->next = $node_3;
$node_3->next = $node_4;
$node_4->next = $node_5;

$node_6 = new ListNode(1);
$node_7 = $node_6;
$node_7 = $node_5;
var_dump($node_6, $node_7, $node_6 === $node_7);